package B刷题.A栈和队列;

import java.util.Stack;

/**
 * @author wei.zhao
 * @description: 程序员代码面试指南：求最大子矩阵的大小
 * @date 2022/12/7 14:33
 */
public class Code10_MaxRecSize {

    /**
     * 注意：
     * 1.重复值的处理：当前高度与栈顶高度相同，栈顶也弹出，栈顶位置面积虽然计算小了，
     *   但是后面相同高度计算的是对的，简化了重复值的处理！
     * 2.宽度的计算：找到最左边小于当前高度索引leftMin、右边小于当前高度索引rightMin，宽度=rightMin-leftMin-1；
     *   左边没有小于的索引那左边就是-1啊，右边没有小于的索引那右边就是arr.length啊，小于的索引实际代表的是不能取到的索引位，
     *   这样统一处理起来更加简单。
     */
    public static int maxRecSize(int[][] map) {
        int result = 0;
        if (null == map || map.length == 0 || map[0] == null || map[0].length == 0) {
            return result;
        }
        // 当前层以每一个数为底上面1的个数，包含当前数
        int[] heights = new int[map[0].length];
        for (int[] ints : map) {
            for (int i1 = 0; i1 < ints.length; i1++) {
                heights[i1] = ints[i1] == 0 ? 0 : heights[i1] + 1;
            }
            result = Math.max(result, maxRecFromBootom(heights));
        }
        return result;
    }

    private static int maxRecFromBootom(int[] heights) {
        int result = 0;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < heights.length; i++) {
            // 只要当前值小于栈顶的元素，栈顶弹出
            while (!stack.isEmpty() && heights[i] <= heights[stack.peek()]) {
                Integer pop = stack.pop();
                // 计算以当前高度为矩形的最大面积
                int leftMin = stack.isEmpty() ? -1 : stack.peek();
                int curArea = heights[pop] * (i - leftMin - 1);
                result = Math.max(result, curArea);
            }
            stack.add(i);
        }
        // 栈全部弹出，直至空
        while (!stack.isEmpty()) {
            Integer pop = stack.pop();
            int leftMin = stack.isEmpty() ? -1 : stack.peek();
            int curArea = heights[pop] * (heights.length-1 - leftMin);
            result = Math.max(result, curArea);
        }
        return result;
    }

}
